In this paper, we propose an end-to-end graph learning framework, namely \textbf{I}terative \textbf{D}eep \textbf{G}raph \textbf{L}earning (\alg), for jointly and iteratively learning graph structure and graph embedding. The key rationale of \alg is to learn a better graph structure based on better node embeddings, and vice versa (i.e., better node embeddings based on a better graph structure). Our iterative method dynamically stops when the learned graph structure approaches close enough to the graph optimized for the downstream prediction task. In addition, we cast the graph learning problem as a similarity metric learning problem and leverage adaptive graph regularization for controlling the quality of the learned graph. Finally, combining the anchor-based approximation technique, we further propose a scalable version of \alg, namely \salg, which significantly reduces the time and space complexity of \alg without compromising the performance. Our extensive experiments on nine benchmarks show that our proposed \alg models can consistently outperform or match the state-of-the-art baselines. Furthermore, \alg can be more robust to adversarial graphs and cope with both transductive and inductive learning.

Summary and Contributions: In this paper, the author presented a new graph learning method for graph neural networks. The authors started to analyze the significant drawbacks of existing GNNs methods: 1. work only when the graph data input is given; 2. ignore potentially imperfect graph inputs (due to the noise and cannot reflect true graph topology); 3. completely fail when inputs like texts are not given in graph format. To solve these problems, this paper proposed a new deep graph learning framework for learning the graph embedding and graph structure at the same time. Specifically, this paper introduced an iterative deep graph learning approach, where the key idea is to alternatively produce a better and more robust graph node embedding with a better learned graph structure and then learn a better graph structure based on better graph node embeddings. They further proposed a scalable version of the proposed method IDGL by leveraging the anchor-based approximation method. Graph similarity learning and graph regularization are also proposed to learn a graph structure with controlled quality, instead of learning a fully connected graph in existing methods.

This paper focuses on the problem of how to develop a (scalable) graph learning technique, which has been underexplored in the domain. The proposal is a novel end-to-end graph learning framework to joint learn graph structure and graph embeddings. The philosophy behind sounds quite interesting to me, namely, sparsified graph over the fully connected graph by performing epsilon-neighborhood and adaptive graph regularization. This philosophy leads to a novel algorithm design I have never seen, i.e., Iterative Deep Graph Learning (IDGL). More importantly, IDGL can cope with both transductive and inductive settings, where the learned embeddings can be applied for many tasks.

In this paper, we propose an end-to-end graph learning framework, namely \textbf{I}terative \textbf{D}eep \textbf{G}raph \textbf{L}earning (\alg), for jointly and iteratively learning graph structure and graph embedding. The key rationale of \alg is to learn a better graph structure based on better node embeddings, and vice versa (i.e., better node embeddings based on a better graph structure). Our iterative method dynamically stops when the learned graph structure approaches close enough to the graph optimized for the downstream prediction task. In addition, we cast the graph learning problem as a similarity metric learning problem and leverage adaptive graph regularization for controlling the quality of the learned graph. Finally, combining the anchor-based approximation technique, we further propose a scalable version of \alg, namely \salg, which significantly reduces the time and space complexity of \alg without compromising the performance.